#include "string_array.h"
#include <iostream>
#include <cstring>
using namespace std;

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}

myStr::myStr(const char* s) {
    if(s == nullptr) {
        data = nullptr;
        length = 0;
        next = nullptr;
        nextVal = nullptr;
        return;
    }
    length = strlen(s);
    data = new char[length + 1];
    strcpy(data, s);
    next = new int[length];
    nextVal = new int[length];
}

myStr::~myStr() {
    delete[] data; data = nullptr;
    length = 0;
    delete[] next; next = nullptr;
    delete[] nextVal; nextVal = nullptr;
}

myStr::myStr(const myStr& str) {
    length = str.length;
    if (str.data) {
        data = new char[length + 1];
        strcpy(data, str.data);
    } else {
        data = nullptr;
    }

    if (length > 0) {
        next = new int[length];
        nextVal = new int[length];
        memcpy(next, str.next, sizeof(int) * length);
        memcpy(nextVal, str.nextVal, sizeof(int) * length);
    } else {
        next = nullptr;
        nextVal = nullptr;
    }
}

void myStr::kmp_next() {
    next[0] = -1;
    next[1] = 0;
    int i = 2, cur_num = 0;
    while(i < length) {
        if(data[i - 1] == data[cur_num]) {
            next[i ++] = ++cur_num;
        } else if(cur_num > 0) {
            cur_num = next[cur_num];
        } else {
            next[i ++] = 0;
        }
    }
    for(int i = 0; i < length; i ++) {
        next[i] ++;
    }
}

void myStr::kmp_nextVal() {
    nextVal[0] = -1;
    for(int k = 0; k < length; k ++) {
        next[k] --;
    }
    for(int i = 0; i < length; i ++) {
        if(data[i] == data[next[i]]) {
            nextVal[i] = nextVal[next[i]];
        } else {
            nextVal[i] = next[i];
        }
    }
    for(int i = 0; i < length; i++) {
        nextVal[i]++;
    }
    for(int k = 0; k < length; k ++) {
        next[k] ++;
    }
}

int kmpMatch(const myStr& str1, const myStr& str2) {
    int i = 0, j = 0;
    myStr tmp(str2);
    tmp.kmp_next();
    tmp.kmp_nextVal();
    for(int k = 0; k < str2.length; k ++) {
        tmp.nextVal[k]--;
    }
    while (i < str1.length && j < str2.length) {
        //j == -1控制是否越界
        //后半条件控制相等 跳转条件
        if (j == -1 || str1.data[i] == str2.data[j]) {
            i++;
            j++;
        } else {
            j = tmp.nextVal[j];
        }
    }
    return (j == str2.length) ? (i - j + 1) : -1;
}

int simpleMatch(const myStr& str1, const myStr& str2) {
    for (int i = 0; i <= str1.length - str2.length; i++) {
        int j = 0;
        while (j < str2.length && str1.data[i + j] == str2.data[j]) {
            j++;
        }
        if (j == str2.length) {  
            return i + 1;
        }
    }
    return -1; 
}


bool replaceStr(myStr& str, const int& start, const myStr& ori_str, const myStr& rep_str) {
    
    int start_Index = start - 1;
    myStr tmp(ori_str);
    tmp.kmp_next();
    tmp.kmp_nextVal();


    //提取右串，防止直接搜索找不到start之后位置的字符串
    char right[str.length - start_Index];
    strncpy(right, str.data + start_Index, str.length - start_Index);
    right[str.length - start_Index] = '\0';

    myStr right_str(right);
    int find_str = kmpMatch(right_str, tmp);
    if(find_str == -1) {
        return false;
    }

    int ori_loc = find_str + start_Index - 1;
    int diff = rep_str.length - ori_str.length;

    //先挪位置，再换
    if(diff > 0) {
        for (int i = str.length - 1; i >= ori_loc + ori_str.length; i--) {
            str.data[i + diff] = str.data[i];
        }
    }
    else if(diff < 0) {
        for(int i = ori_loc + ori_str.length; i <= str.length; i++) {
            str.data[i + diff] = str.data[i];
        }
    }

    for(int i = 0; i < rep_str.length; i++) {
        str.data[ori_loc + i] = rep_str.data[i];
    }
    
    str.length += diff;
    str.data[str.length] = '\0';
    return true;
}


myMatrix::myMatrix() {
    rowNum = colNum = nodeNum = 0;
    nodeList = nullptr;
}

myMatrix::myMatrix(const int& row_num, const int& col_num, const int& n_num, const int* data) {
    rowNum = row_num;
    colNum = col_num;
    nodeNum = n_num;
    int i = 0;
    nodeList = new matrixNode[n_num];
    while(i < n_num) {
        nodeList[i].row = data[i * 3];
        nodeList[i].col = data[i * 3 + 1];
        nodeList[i].value = data[i * 3 + 2];
        i++;
    }
}

myMatrix::~myMatrix() {
    delete[] nodeList;
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
}


void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = colNum;
    T.colNum = rowNum;
    T.nodeNum = nodeNum;
    T.nodeList = new matrixNode[nodeNum];

    int* nums = new int[colNum]{0};
    int* cpot = new int[colNum]{0};

    for (int i = 0; i < nodeNum; i++)
        nums[nodeList[i].col]++;

    cpot[0] = 0;
    for (int i = 1; i < colNum; i++)
        cpot[i] = cpot[i - 1] + nums[i - 1];

    for (int i = 0; i < nodeNum; i++) {
        int col = nodeList[i].col;
        int pos = cpot[col];
        T.nodeList[pos].row = nodeList[i].col;
        T.nodeList[pos].col = nodeList[i].row;
        T.nodeList[pos].value = nodeList[i].value;
        cpot[col]++;
    }

    delete[] nums;
    delete[] cpot;
}